学习同态加密：第二代全同态加密经典论文合集

全同态加密领域的首创者是Gentry，他做出的开创性工作的为三个主要的全同态加密研究阶段的铺平了道路。

本文会按照全同态加密经典论文的研究阶段进行划分，并给出相关的阅读建议。

对于第一代全同态加密经典论文的合集，请各位同学参考学习同态加密：第一代全同态加密经典论文合集。

有兴趣的同学还可以阅读往期推送，了解更多全同态加密的知识体系整理，详情请请见全同态加密知识体系整理(上)和全同态加密知识体系整理(下)。

1

第二代：基于LWE和RLWE的FHE

ab

经典论文

2011年，Brakerski和Vaikuntanathan利用自举技术，介绍了基于LWE和RLWE问题和循环安全假设的两种FHE方案。

Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE,” in Proc. IEEE 52nd Annu. Symp. Found. Comput.Sci., Oct. 2011, pp. 97–106.

Z. Brakerski and V. Vaikuntanathan, “Fully homomorphic encryption from ring-LWE and security for key dependent messages,” in Advances in Cryptology—CRYPTO 2011, P. Rogaway, Ed.Berlin, Germany: Springer, 2011, pp. 505–524.

这些工作开启了第二代FHE计划，其中基于LWE的对称方案，称为BV。

Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE,”

SIAM J. Comput., vol. 43, no. 2, pp. 831–871, 2014.

之后，Brakerski和Vaikunthanathan提出了一种新版本的BV方案，其中方案的安全性基于多项式LWE (PLWE)问题。

Z. Brakerski and V. Vaikuntanathan, “Fully homomorphic encryption from ring-LWE and security for key dependent messages,” in Advances in Cryptology—CRYPTO 2011, P. Rogaway, Ed.Berlin, Germany: Springer, 2011, pp. 505–524.

Brakerski等提出了一种定义层次化全同态方案的方法，该方法避免了计算代价高昂的自举技术。在此基础上，他们定义了BGV方案。

Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without

bootstrapping,” ACM Trans. Comput. Theory, vol. 6, no. 3, pp. 1–36, Jul. 2014.

这种新方法使该方案适用于实际场景，从而引起了研究界越来越大的兴趣。作者介绍了BGV方案的两种变体(一种基于LWE假设，另一种基于RLWE假设)。方案1中描述的基于RLWE的BGV方案比LWE方案更有效，它在广泛使用的FHE库HElib中进行实现。

该库的架构是基于BGV方案的一种变体，该方案引入了一些优化，由Gentry等人提出，用于AES电路的具体实现。

C. Gentry, S. Halevi, and N. P. Smart, “Homomorphic evaluation of the AES circuit,” in Advances in Cryptology—CRYPTO 2012, R. Safavi-Naini and R. Canetti, Eds. Berlin, Germany: Springer, 2012, pp. 850–867.

F. Maino, U. Blumenthal, and K. McCloghrie, The Advanced Encryption Standard (AES) Cipher Algorithm in the SNMP User-Based Security Model, document RFC 3826, 2004. [Online]. Available: https://rfc-editor.org/rfc/rfc3826.txt

此外，Gentry等人使用Smart和Vercauteren以及Brakerski等人的批处理技术，提供了渐近最快的方案，对快速自举有显著影响。

C. Gentry, S. Halevi, and N. P. Smart, “Fully homomorphic encryption with polylog overhead,” in Advances in Cryptology—EUROCRYPT 2012, D. Pointcheval and T. Johansson, Eds. Berlin, Germany: Springer, 2012, pp. 465–482.

Brakerski基于一种称为尺度不变量(Scale-Invariant)的技术提供了另一种BGV方案。这种技术减少了同态乘法从指数乘法到线性乘法所产生的误差增加。

Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical GapSVP,” in Advances in Cryptology—CRYPTO 2012, R. Safavi-Naini and R. Canetti, Eds. Berlin, Germany: Springer, 2012, pp. 868–886.

Brakerski方案的RLWE版本由Fan和Vercauteren实施和优化，并命名为FV方案。

J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” Cryptol. ePrint Arch., Paper 2012/144, 2012. [Online]. Available: https://eprint.iacr.org/2012/144

在接下来的章节中，我们将这两种方案称为B/FV方案，即LWE/RLWE变体。FV方案是微软简单加密算术库(Simple Encrypted Arithmetic Library, SEAL)中实现的三种方案之一，它允许对加密的整数执行模块化算术。

沿着这条研究路线，Bajard等提出了一种密文系数较大时的优化方法，称为RNS FV (BEHZ变体)。它是基于余数系统(RNS)，因为它使用CRT表示法。

J.-C. Bajard, J. Eynard, M. A. Hasan, and V. Zucca, “A full RNS variant of FV like somewhat homomorphic encryption schemes,” in Proc. Int. Conf. Sel. Areas Cryptogr. Cham, Switzerland: Springer, 2016, pp. 423–442.

Halevi等人在随后的研究中对该变体进行了改进(HPS变体)。

S. Halevi, Y. Polyakov, and V. Shoup, “An improved RNS variant of the BFV homomorphic encryption scheme,” in Proc. Cryptographers’ Track RSA Conf. Cham, Switzerland: Springer, 2019, pp. 83–105.

Al Badawi等人对这两种方法进行了评估，作者表明HPS变体相对于具有更好的解密和同态乘法运行时。

A. Al Badawi, Y. Polyakov, K. M. M. Aung, B. Veeravalli, and K. Rohloff, “Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme,” IEEE Trans. Emerg. Topics Comput., vol. 9, no. 2, pp. 941–956, Apr. 2021.

然而，Bajard等人对这项工作的后续注释表明，BEHZ和HPS变体的噪声增长实际上非常接近，HPS提供的运行时间仅略好于BEHZ。

J. C. Bajard, J. Eynard, P. Martins, L. Sousa, and V. Zucca, “Note on the noise growth of the RNS variants of the BFV scheme,” Cryptol. ePrint Arch., 2019.

Chen和Han改进了BGV和FV方案的自举技术，以获得大明文模量(即大素数幂)。

H. Chen and K. Han, “Homomorphic lower digits removal and improved FHE bootstrapping,” in Advances in Cryptology—EUROCRYPT 2018, J. B. Nielsen and V. Rijmen, Eds. Cham, Switzerland: Springer, 2018, pp. 315–337.

在此基础上，Halevi和Shoup提出了BGV的改进变体，该变体由同一作者在HElib中实现。

S. Halevi and V. Shoup, “Faster homomorphic linear transformations in HElib,” in Proc. Annu. Int. Cryptol. Conf. Cham, Switzerland: Springer, 2018, pp. 93–120.

Chen等人提出了对FV方案的另一种修改。

H. Chen, K. Laine, R. Player, and Y. Xia, “High-precision arithmetic in homomorphic encryption,” in Proc. Cryptographers’ Track RSA Conf. Cham, Switzerland: Springer, 2018, pp. 116–136.

最近在中给出了这项工作的推广，其中Bootland等人提出了明文模数的改进。

C. Bootland, W. Castryck, I. Iliashenko, and F. Vercauteren, “Efficiently processing complex-valued data in homomorphic encryption,” J. Math. Cryptol., vol. 14, no. 1, pp. 55–65, Jun. 2020.

这两项工作，都是在一系列文章之后，研究了将真实输入数据(即整数，有理或复数)转换为多项式的编码方法，该多项式是RLWE方案的消息空间(即明文)的一个元素。

S. Arita and S. Nakasato, “Fully homomorphic encryption for point numbers,” in Proc. Int. Conf. Inf. Secur. Cryptol. Cham, Switzerland: Springer, 2016, pp. 253–270.

C. Bonte, C. Bootland, J. W. Bos, W. Castryck, I. Iliashenko, and F. Vercauteren, “Faster homomorphic function evaluation using non-integral base encoding,” in Proc. Int. Conf. Cryptograph. Hardw. Embedded Syst. Cham, Switzerland: Springer, 2017, pp. 579–600.

A. Jäschke and F. Armknecht, “Accelerating homomorphic computations on rational numbers,” in Proc. Int. Conf. Appl. Cryptogr. Netw. Secur. Cham, Switzerland: Springer, 2016, pp. 405–423.

值得强调的是，与原始版本的FV方案相比，Chen等人和Bootland等人都实现了误差增长的减少，因此，它们都能够评估具有更高乘法深度的电路。

这两种方法的主要区别在于，Chen等人编码的是小数，而Bootland等人编码的是复数。

在BGV和B/FV方案中(在其他FHE方案中也类似)，每个密文都包含一个误差，随着每次同态操作的增长而增长。

为了避免解密失败，错误必须低于某个阈值。这意味着在影响参数选择的安全级别和误差范围之间进行权衡，这是特定于每个用例的。

这样的参数选择需要对误差增长进行复杂的研究，这激发了一些研究工作。

即，Costache等人扩展了之前对Costache和Smart的性能评估，比较了BGV和FV方案的误差增长。具体而言，Costache等证明，对于特定的小明文模量和电路深度，BGV比FV需要更大的参数集。

A. Costache, K. Laine, and R. Player, “Evaluating the effectiveness of heuristic worst-case noise analysis in FHE,” in Proc. Eur. Symp. Res. Comput. Secur. Cham, Switzerland: Springer, 2020, pp. 546–565.

另一方面，当明文模量为中等或较大时，BGV优于FV。然而，在中进行的分析没有考虑BGV和FV的一些可用优化。

Mono等人在之前的研究基础上提供了一种动态(即依赖于水平的)噪声估计，但也考虑了BGV的新特征。此外，他们还提供了一个易于使用的交互式参数生成器工具。

J. Mono, C. Marcolla, G. Land, T. Güneysu, and N. Aaraj, “Finding and evaluating parameters for BGV,”Cryptol. ePrint Arch., 2022.

Kim等人提出了对FV和BGV方案的几种优化，并提出了一种不同的方法来计算BGV方案的密文模量，该方法不需要动态噪声估计，但以增加密文模量为代价。

A. Kim, Y. Polyakov, and V. Zucca, “Revisiting homomorphic encryption schemes for finite fields,” in Advances in Cryptology—ASIACRYPT, vol. 13092, M. Tibouchi and H. Wang, Eds. Springer, 2021, pp. 608–639.

通过这些优化，对于所有明文模，它们的FV变体比BGV具有更好的噪声增长。然而，它们的FV变体仅在小明文中比BGV快，而BGV在中间和大明文中仍然更快。

2

第二代：基于NTRU的FHE

经典论文

NTRU是Hoffstein等人于1996年引入的基于格的加密方案，并于2000年申请了临时专利，并于2000年获得授权。

J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A ring-based public key cryptosystem,” in Proc. Int. Algorithmic Number Theory Symp. Cham, Switzerland: Springer, 1998, pp. 267–288.

自提出以来，该方案的安全性一直受到研究界的讨论，直到2011年，stehl对该方案进行了轻微修改，以获得基于RLWE假设的安全性变体。

D. Stehlé and R. Steinfeld, “Making NTRU as secure as worst-case problems over ideal lattices,” in Advances in Cryptology—EUROCRYPT 2011, K. G. Paterson, Ed. Berlin, Germany: Springer, 2011, pp. 27–47.

一年后，López-Alt等人引入了受stehl - steinfeld NTRU变体启发的第一个FHE方案。

A. López-Alt, E. Tromer, and V. Vaikuntanathan, “On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption,” in Proc. 44th Symp. Theory Comput., 2012,pp. 1219–1234.

它被认为是第二代FHE计划的一部分。具体来说，作者提出了一种称为多密钥FHE的同态加密方案的新概念，它支持对不同密钥加密的密文进行计算。

一年后，Bos等人修改了LTV方案，提出了两种方案:

1)Yet Another Somewhat Homomorphic Encryption (YASHE)方案，他们使用规模不变量去除了DSPR假设，代价是拥有一个大的评估密钥和一个复杂的密钥交换方法;

2)YASHE版本再次包含DSPR假设，以实现更实用的结构。

J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig, “Improved security for a ring-based fully homomorphic encryption scheme,” in Proc. Int. Conf. Cryptogr. Coding. Cham, Switzerland: Springer, 2013, pp. 45–64.

2016年，Albrecht等人和Cheon等人在一项独立研究中提供了一种攻击，该攻击使得任何基于DSPR问题的类ntru方案对于某些特定参数的选择都是不安全的。

M. Albrecht, S. Bai, and L. Ducas, “A subfield lattice attack on overstretched NTRU assumptions,” in Advances in Cryptology—CRYPTO 2016, M. Robshaw and J. Katz, Eds. Berlin, Germany: Springer, 2016.

J. H. Cheon, J. Jeong, and C. Lee, “An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero,” LMS J. Comput. Math., vol. 19, no. A, pp. 255–266, 2016.

最后，Doröz和Sunar通过去除DSPR假设，使GSW方案适应NTRU设置。

Y. Doröz and B. Sunar, “Flattening NTRU for evaluation key free homomorphic encryption,” IACR Cryptol. ePrint Arch., vol. 2016, p. 315, Dec. 2016.

虽然ntru类方案总体上比RLWE方案快，但Lepoint和Naehrig的研究表明，FV方案的误差低于YASHE方案。

T. Lepoint and M. Naehrig, “A comparison of the homomorphic encryption schemes FV and YASHE,” in Proc. Int. Conf. Cryptol. Afr. Cham, Switzerland: Springer, 2014, pp. 318–335.

此外，Kim和Lauter证明了YASHE在低阶计算时优于BGV，但在高电路深度时，BGV比YASHE更有效。

M. Kim and K. Lauter, “Private genome analysis through homomorphic encryption,” in BMC Medical Informatics and Decision Making, vol. 15, no. 5. London, U.K.: BioMed Central, 2015, pp. 1–12.

3

学习建议

第二代全同态加密文章数量较多，其中经典文章主要以BGV以及BFV等为主，建议优先阅读[Revisiting Homomorphic Encryption Schemes for Finite Fields，Which Ring Based Somewhat Homomorphic Encryption Scheme is Best]，且BGV以及BFV对于后续的第三代全同态加密的发展也有较大的推进作用。

END

往期推荐

1.文章速览 | 联邦学习 x AAAI'2023 （下）
2.深入浅出零知识证明（二）：电路模型概述3.文章速览 | 联邦学习 x AAAI'2023 （上）4.论文分享 | 基于全同态加密的跨边缘区块链网络隐私保护方案